package MonotonicStack;

import org.junit.jupiter.api.Test;

import java.util.EnumSet;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class trap_ {

  @Test
  public void trapTest(){
    int[] height = new int[]{60,20,20,10,30};

    System.out.println(trap(height));
  }

  // 接雨水
  // 找到当前柱子右边比他大的柱子和左边比他大的柱子分别是哪一个
  public int trap(int[] height) {
    int sum = 0;
    int h = 0;
    int w = 0;
    int[] leftResult = new int[height.length];
    int[] rightResult = new int[height.length];
    Stack<Integer> stack = new Stack<>();

    stack.push(0);

    for (int i = 1 ; i < height.length ; i++){
      if (height[i] <= height[stack.peek()]){
        stack.push(i);
      }
      else{
        while(!stack.isEmpty() && height[i] > height[stack.peek()]){
          int H = stack.pop();
          if (!stack.isEmpty()){
            h = Math.min(height[i],height[stack.peek()]) - height[H];
            w = i - stack.peek() - 1;
            sum += h * w;
          }
        }
        stack.push(i);
      }
    }
    return sum;
  }
}
